package 高频题;

public class 跳跃游戏II_45 {

    public static void main(String[] args) {
        System.out.println(new 跳跃游戏II_45().jump(new int[]{2,3,1,1,4}));
    }

    public int jump(int[] nums) {
        int n = nums.length;
        //站在索引i最多能挑到索引end
        int end = 0;
        //从索引[i...end]起跳，能到达的最远距离
        int farthest = 0;
        //记录跳跃的次数
        int jumps = 0;
        for (int i = 0; i < n - 1; i++) {
            farthest = Math.max(nums[i] + i, farthest);
            if (end == i) {//即当前这个区间走完
                //如果还是不能理解就看书P.380的那幅图
                jumps++;//那就要跳第二步了。
                end = farthest;
            }
        }
        return jumps;
    }
}
